package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_131_PalindromePartitioning {
    public static void main(String[] args) {

    }

    static class Solution {

        public List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList<>();
            List<String> temp = new ArrayList<>();
            dfs(s, 0, temp, result);
            return result;
        }

        private void dfs(String s, int curIndex, List<String> temp, List<List<String>> result) {
            if (curIndex == s.length()) {
                result.add(new ArrayList<>(temp));
                return;
            }
            for (int i = curIndex + 1; i <= s.length(); i++) {
                String prefix = s.substring(curIndex, i);
                if (!isPrlindrome(prefix))
                    continue;
                temp.add(prefix);
                dfs(s, i, temp, result);
                temp.remove(temp.size() - 1);
            }
        }

        private boolean isPrlindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                if (s.charAt(left) != s.charAt(right))
                    return false;
                left++;
                right--;
            }
            return true;
        }

    }
}
